package 每日一题;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class 求众数2 {
//方法1： map 统计每个数字出现的次数
//方法2： 摩尔投票
//方法3： 滑动窗口
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        int n = nums.length;
        if (n == 1) {
            list.add(nums[0]);
            return list;
        }
        Arrays.sort(nums);
        int i = 0, j = 1;
        while (i < n) {
            int num = 1;
            if (j < n) {
                while (nums[j] == nums[i]) {
                    num++;
                    j++;
                    if (j == n)
                        break;
                }
            }
            if (num > n / 3)
                list.add(nums[i]);
            i = j;
            j = i + 1;
        }
        return list;
    }
}
